import java.util.Scanner;

public class DuplicationInArray {
    public static void main(String[] arg)
    {
        Scanner in = new Scanner(System.in);
        int length;
        System.out.println("Set the array length: ");
        length = in.nextInt();
        int[] arr = new int[length];
        System.out.println("the array value: ");
        for(int i = 0; i < length; i++)
            arr[i] = in.nextInt();
        int res = getDuplication(arr);
        System.out.println(res);
    }
    public static int getDuplication(int[] arr)
    {
        if(arr.length <= 0)
            return -1;

        int start = 1;
        int end = arr.length - 1;

        while(start <= end)
        {
            int middle = ((end - start) >> 1) + start;
            int count = countRange(arr, start, middle);
            if(end == start)
            {
                if(count > 1)
                    return start;
                else
                    break;
            }
            if(count > (middle - start + 1))
                end = middle;
            else
                start = middle + 1;
        }
        return -1;
    }
    public static int countRange(int[] arr, int start, int end)
    {
        int count = 0;
        for(int element : arr)
        {
            if(element >= start && element <= end)
                count++;
        }
        return count;
    }
}
